# Definition for a binary tree node.
from typing import List, Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if len(preorder) == 0 or len(postorder) == 0:
            return None
        if len(preorder) == 1 or len(postorder) == 1:
            return TreeNode(val=preorder[0], left=None, right=None)

        val = preorder[0]
        left_val = preorder[1]
        idx = postorder.index(left_val)

        left_len = idx + 1
        pre_left = preorder[1:1 + left_len]
        pre_right = preorder[1 + left_len:len(preorder)]
        post_left = postorder[0:idx + 1]
        post_right = postorder[idx + 1:len(postorder) - 1]

        node = TreeNode(val=val,
                        left=self.constructFromPrePost(pre_left, post_left),
                        right=self.constructFromPrePost(pre_right, post_right))
        return node
